package com.zj.leetcode.medium.binarySearch;

/**
 * @program: algorithm
 * @description: 搜索二维矩阵
 * 74 search-a-2d-matrix
 * @author: Zhang Bo
 * @create: 2022-04-28 14:20:15
 **/
public class SearchA2dMatrix {
    public static void main(String[] args) {
//        int[][] matrix = {{1,3,5,7},{10,11,16,20},{23,30,34,60}};
        int[][] matrix = {{3}};
        int target = 3;
        Solution solution = new SearchA2dMatrix().new Solution();
        System.out.println(solution.searchMatrix(matrix, target));
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public boolean searchMatrix(int[][] matrix, int target) {
            int len = matrix[matrix.length - 1].length - 1;
            for (int i = 0; i < matrix.length; i++) {
                if (matrix[i][len] > target) {
                    return this.binarySearch(matrix[i], target);
                } else if(matrix[i][len] == target){
                    return true;
                }
            }
            return false;
        }

        private boolean binarySearch(int[] nums, int target) {
            int l = 0;
            int r = nums.length - 1;
            while (l <= r) {
                int mid = (r - l) / 2 + l;
                if (nums[mid] == target) {
                    return true;
                } else {
                    if (nums[mid] > target) {
                        r = mid - 1;
                    } else {
                        l = mid + 1;
                    }
                }
            }
            return false;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}